package letcode.oneQuestionPerDay._202004._16;

import java.util.*;

/**
 * @Description: 合并区间
 * @Date: 2020/4/16
 * @Author: 许群星
 */
public class MergingInterval {
    public static void main(String[] args) {
        int[][] a = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] a1 = {{1,4},{4,5}};
        int[][] a2 = {{1,4},{0,2},{3,5}};
        int[][] haha = merge(a);
        for (int i = 0; i < haha.length; i++) {
            System.out.println(haha[i][0] + "," + haha[i][1] + "|");
        }

    }

    //提交
    public static int[][] merge(int[][] intervals) {
        int n = intervals.length;
        int[][] ans=new int[n][2];
        List<Integer> list=new ArrayList<>();

        //边缘情况
        if (n==1)
            return intervals;
        
        //将数组按照第一个元素的顺序排序 升序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]==o2[0])
                    return o1[1]-o2[1];
                return o1[0]-o2[0];
            }
        });

        //处理   切分区块  合并
        int m=-1;
        for (int[] ints:intervals) {
            //如果结果数组为空，或者当前区间的起始位置》结果数组中最后一个区间的所有位置的数
            //直接将当前区间加入结果数组
            if (m==-1||ints[0]>ans[m][1]){
                ans[++m]=ints;
            }else {
                //将当前区间合并至结果数组的最后区间
                ans[m][1]=Math.max(ans[m][1],ints[1]);
            }
        }
        return Arrays.copyOf(ans,m+1);
    }
}
/*
给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: {{1,3},{2,6},{8,10},{15,18}}
输出: {{1,6},{8,10},{15,18}}
解释: 区间 {1,3} 和 {2,6} 重叠, 将它们合并为 {1,6}.
示例 2:

输入: {{1,4},{4,5}}
输出: {{1,5}}
解释: 区间 {1,4} 和 {4,5} 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */